package problems;

import lib.Fraction;
import lib.MathLib;


/**
 * Considering that every hexagonal number is also triangular, the problem reduces to finding the third
 * 5-and-6-gonal number (PH_3), the second being given as 40755 and the first being 1, trivially.
 * 
 * This program is based on the solution on http://mathworld.wolfram.com/HexagonalPentagonalNumber.html.
 * 
 * P_n = H_m
 * 1/2 n (3n - 1) = m (2m - 1)
 * completing the square gives (6n - 1)^2 - 3(4m - 1)^2 = -2
 * defining x as 6n - 1 and y as 4m - 1 gives x^2 - 3 y^2 = -2.
 * Solve this Pell-like equation by Diophantine analysis to find integer n and m.
 * The third pair gives the index numbers for for PH_3.
 * 
 * @author laszlo
 *
 */
public class Euler045 extends AbstractEuler {

	@Override
	public Number calculate() {
		long x = 0, y = 0;
		long integerSolutionsFound = 0;
		Fraction n, m;

		do {
			x++; y++; //because we haven't found enough solutions yet
			
			long calculation;
			do {
				calculation = x*x - 3*y*y;
				if (calculation > -2) {
					y++; 
				} else if (calculation < -2) {
					x++;
				}
			} while (calculation != -2);
//			System.out.println("found another solution pair: (" + x + "," + y + ")");
			
			//calculate n and m from the x and y for HP3 
			
			n = new Fraction(x + 1, 6).normalized();
			m = new Fraction(y + 1, 4).normalized();
			
			if (n.isInteger() && m.isInteger()) {
//				System.out.println("\tand they yield integer n and m: (" + n + "," + m + ")");
				integerSolutionsFound++;
			}
			
		} while (integerSolutionsFound < 3);
		
		return MathLib.getPolygonalNumber(m.getNumerator(), 6).longValue();

	}
	

	@Override
	/**
	 * @see http://oeis.org/A046180
	 * 
	 */
	protected Number getCorrectAnswer() {
//		pentagonal number 31977 = hexagonal number 27693 = 5/6-gonal number 3 = 1533776805
		return 1533776805L;
	}

}
